package crazy;

public class ShellSort
{

	public static void main(String[] args)
	{
		DataWrap[] data = { new DataWrap(9, ""), new DataWrap(-16, ""),
				new DataWrap(21, "*"), new DataWrap(23, ""),
				new DataWrap(-30, ""), new DataWrap(-49, ""),
				new DataWrap(21, ""), new DataWrap(30, "*"),
				new DataWrap(30, "") };

		System.out.println("before sorting-->"+java.util.Arrays.toString(data));
		shellSort(data);
		System.out.println("after sorting-->"+java.util.Arrays.toString(data));
	}
	
	public static void shellSort(DataWrap[] data)
	{
		int arrayLength = data.length;
		
		int h = 1;
		while (h<=arrayLength/3)
		{
			h = h*3+1;
		}
		while (h>0)
		{
			System.out.println("=====h-->"+h+"=====");
			for (int i = h; i < arrayLength; i++)
			{
				DataWrap tmp = data[i];
				if (data[i].compareTo(data[i-h])<0)
				{
					int j = i -h;
					for (; j>=0 && data[j].compareTo(tmp)>0; j=j-h)
					{
						data[j+h] = data[j];
					}
					data[j+h] = tmp;
				}
				System.out.println(java.util.Arrays.toString(data));
			}
			h = (h-1)/3;
		}
	}

}
